package com.mashibing.class27;


public class Code01_KMP {
    public static int getIndexOf(String s1, String s2) {
    if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
        return -1;
    }
    System.out.println("s1 = " + s1);
    System.out.println("s2 = " + s2);
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int x = 0; // 在str1中画圈的位置.
    int y = 0; // 在str2中画圈的位置.
    // O(M) m <= n
    int[] next = getNextArray(str2);
        // O(N)
    while (x < str1.length && y < str2.length) {
        if (str1[x] == str2[y]) {
            x++;
            y++;
        } else if (next[y] == -1) { // y == 0 , next的值不能再继续往左跳了
            x++;
        } else { // y的值会往前跳.
            y = next[y];
        }
    }
    return y == str2.length ? x - y : -1;
}

    public static int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[str2.length];
        next[0] = -1;// 0位置一定是是 -1
        next[1] = 0; // 1位置一定是 0
        int i = 2; // 目前在哪个位置上求next数组的值
        int cn = 0; // 当前是哪个位置的值 再和 i-1位置的字符 比较.
        while (i < next.length) {
            // 0位置的字符 跟 1位置的字符 进行相比.
            // cn    i-1   相等
            // 0      1   next[2] = 1
            // 1      2   next[3] = 2
            // 2      3   next[4] = 3
            // ....
            if (str2[i - 1] == str2[cn]) { // 配成功的时候
                next[i++] = ++cn;// next的i位置的值是 cn+1的值.
            } else if (cn > 0) { // cn能够继续往左跳的话, 继续往左跳 (没有匹配成功)
                cn = next[cn];
            } else { // cn 无法继续王座跳了, 他的next[i++]的值就为0. (没有匹配成功)
                next[i++] = 0;
            }
        }
        return next;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 1;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            System.out.println("str = " + str);
            System.out.println("match = " + match);
            if (getIndexOf(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}
